{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Next Palindrome Using Same Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nextPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下个由相同数字构成的回文串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个很长的数字回文串 <code>num</code> ，返回 <strong>大于</strong> <code>num</code>、<strong>由相同数字重新组合而成的最小</strong> 回文串。</p>\n",
    "\n",
    "<p>如果不存在这样的回文串，则返回空串 <code>\"\"</code>。</p>\n",
    "\n",
    "<p><strong>回文串</strong> 是正读和反读都一样的字符串。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>num = \"1221\"\n",
    "<b>输出：</b>\"2112\"\n",
    "<b>解释：</b>下个比<b> </b>\"1221\" 大的回文串是 \"2112\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>num = \"32123\"\n",
    "<b>输出：</b>\"\"\n",
    "<b>解释：</b>不存在通过重组 \"32123\" 的数字可得、比 \"32123\" 还大的回文串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>num = \"45544554\"\n",
    "<b>输出：</b>\"54455445\"\n",
    "<b>解释：</b>下个比 \"45544554\" 还要大的回文串是 \"54455445\"。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= num.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>num</code> 是回文串。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [next-palindrome-using-same-digits](https://leetcode.cn/problems/next-palindrome-using-same-digits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [next-palindrome-using-same-digits](https://leetcode.cn/problems/next-palindrome-using-same-digits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1221\"', '\"32123\"', '\"45544554\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        n = len(num)\n",
    "        if n==1:\n",
    "            return ''\n",
    "        m = n//2 \n",
    "        s = num[:m]\n",
    "        if n%2==1:\n",
    "            p = num[m]\n",
    "        else:\n",
    "            p = ''\n",
    "        a = []\n",
    "        b = []\n",
    "        for j in range(m)[::-1]:\n",
    "            if a and (s[j]<a[-1]):\n",
    "                while a and (s[j]<a[-1]):\n",
    "                    t = a.pop()\n",
    "                    b.append(t) \n",
    "                st = b.pop()\n",
    "                a.append(s[j]) \n",
    "                a += b \n",
    "                a.sort()\n",
    "                pre = s[:j]\n",
    "                nex = ''.join(a)\n",
    "                pre = pre + st + nex \n",
    "                nex = pre[::-1]\n",
    "                return (pre + p + nex)\n",
    "            a.append(s[j])\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        m = len(num) >> 1\n",
    "        stack, mid = [], num[m] if len(num) & 1 else ''\n",
    "        for i in range(m-1, -1, -1):\n",
    "            j = -1\n",
    "            while stack and num[stack[-1]] > num[i]:\n",
    "                j = stack.pop()\n",
    "            if j >= 0:\n",
    "                x = num[:i] + num[j] + ''.join(sorted(num[i+1:j] + num[i] + num[j+1:m]))\n",
    "                return x + mid + x[::-1]\n",
    "            stack.append(i)\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        n = len(num)\n",
    "        if n <= 1:\n",
    "            return \"\"\n",
    "\n",
    "        half = num[ : n//2]\n",
    "        half = self.get_next_permutation(half)\n",
    "        if half == \"\":\n",
    "            return \"\"\n",
    "\n",
    "        res = half\n",
    "        if n % 2 == 1:      #长度为奇数的情况，要单独加中间的字符\n",
    "            res += num[n//2]\n",
    "        res += half[::-1]\n",
    "\n",
    "        return  res\n",
    "\n",
    "    def get_next_permutation(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return \"\"\n",
    "        i = n - 1\n",
    "        while 0 < i and s[i-1] >= s[i]:\n",
    "            i -= 1\n",
    "        \n",
    "        if i == 0:\n",
    "            return \"\"\n",
    "\n",
    "        l, r = i, n - 1\n",
    "        while l < r:\n",
    "            s[l], s[r] = s[r], s[l]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        for j in range(i, n):\n",
    "            if s[i-1] < s[j]:\n",
    "                s[i-1], s[j] = s[j], s[i-1]\n",
    "                return ''.join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        m = len(num) >> 1\n",
    "        ct, mid = Counter(num[:m]), num[m] if len(num) & 1 else ''\n",
    "        stack = []\n",
    "        for i in range(m-1, -1, -1):\n",
    "            j = -1\n",
    "            while stack and num[stack[-1]] > num[i]:\n",
    "                j = stack.pop()\n",
    "            if j >= 0:\n",
    "                x = num[:i] + num[j] + ''.join(sorted(num[i+1:j] + num[i] + num[j+1:m]))\n",
    "                return x + mid + x[::-1]\n",
    "            stack.append(i)\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        n = len(num)\n",
    "        if n <= 1:\n",
    "            return \"\"\n",
    "\n",
    "        half = num[ : n//2]\n",
    "        half = self.get_next_permutation(half)\n",
    "        if half == \"\":\n",
    "            return \"\"\n",
    "\n",
    "        res = half\n",
    "        if n % 2 == 1:      #长度为奇数的情况，要单独加中间的字符\n",
    "            res += num[n//2]\n",
    "        res += half[::-1]\n",
    "\n",
    "        return  res\n",
    "\n",
    "    def get_next_permutation(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return \"\"\n",
    "        i = n - 1\n",
    "        while 0 < i and s[i-1] >= s[i]:\n",
    "            i -= 1\n",
    "        \n",
    "        if i == 0:\n",
    "            return \"\"\n",
    "\n",
    "        l, r = i, n - 1\n",
    "        while l < r:\n",
    "            s[l], s[r] = s[r], s[l]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        for j in range(i, n):\n",
    "            if s[i-1] < s[j]:\n",
    "                s[i-1], s[j] = s[j], s[i-1]\n",
    "                return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        n = len(num)\n",
    "        if n <= 3:\n",
    "            return \"\"\n",
    "        lst = list(num[:n//2])\n",
    "        for i in range(n//2-1, 0, -1):\n",
    "            if lst[i-1] < lst[i]:\n",
    "                ind = i\n",
    "                for j in range(i+1, n//2):\n",
    "                    if lst[ind] > lst[j] > lst[i-1]:\n",
    "                        ind = j\n",
    "                lst[i-1], lst[ind] = lst[ind], lst[i-1]\n",
    "                lst[i:] = sorted(lst[i:])\n",
    "                ans = \"\".join(lst)\n",
    "                if n % 2:\n",
    "                    ans += num[n//2]\n",
    "                ans += \"\".join(lst[::-1])\n",
    "                return ans\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        \"\"\"\n",
    "        :param num:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def nextPermutation(nums: List[int]) -> None:\n",
    "            i = len(nums) - 2\n",
    "            while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "                i -= 1\n",
    "            if i >= 0:\n",
    "                j = len(nums) - 1\n",
    "                while j >= 0 and nums[i] >= nums[j]:\n",
    "                    j -= 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "\n",
    "            left, right = i + 1, len(nums) - 1\n",
    "            while left < right:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "\n",
    "        left = num[:len(num) // 2]\n",
    "        rigtt_list = [i for i in left]\n",
    "        minval = sorted(rigtt_list)\n",
    "        nextPermutation(rigtt_list)\n",
    "        if minval == rigtt_list:\n",
    "            return ''\n",
    "        ret = rigtt_list\n",
    "        mirror = [i for i in reversed(ret)]\n",
    "        if len(num) % 2 == 0:\n",
    "            ans1 = ''.join(ret) + ''.join(mirror)\n",
    "            return ans1\n",
    "        else:\n",
    "            ans1 = ''.join(ret) + num[len(num) // 2] + ''.join(mirror)\n",
    "            return ans1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.nextPalindrome('23143034132'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        n = len(num)\n",
    "        s = list(num[:n//2])\n",
    "        m = len(s)\n",
    "\n",
    "        i = m - 2\n",
    "        while i >= 0 and s[i] >= s[i+1]:\n",
    "            i -= 1\n",
    "        if i >= 0:\n",
    "            j = m - 1\n",
    "            while j >= 0 and s[i] >= s[j]:\n",
    "                j -= 1\n",
    "            s[i], s[j] = s[j], s[i]\n",
    "        else:\n",
    "            return ''\n",
    "        left, right = i + 1, m - 1\n",
    "        while left < right:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        if n % 2 == 1:\n",
    "            s = s + [num[n//2]] + s[::-1]\n",
    "        else:\n",
    "            s = s + s[::-1]\n",
    "            \n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        \"\"\"\n",
    "\n",
    "        :param num:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        left = num[:len(num) // 2]\n",
    "        rigtt_list = [i for i in left]\n",
    "        minval = sorted(rigtt_list)\n",
    "        self.nextPermutation(rigtt_list)\n",
    "        if minval == rigtt_list:\n",
    "            return ''\n",
    "        ret = rigtt_list\n",
    "        mirror = [i for i in reversed(ret)]\n",
    "        if len(num) % 2 == 0:\n",
    "            ans1 = ''.join(ret) + ''.join(mirror)\n",
    "            return ans1\n",
    "        else:\n",
    "            ans1 = ''.join(ret) + num[len(num) // 2] + ''.join(mirror)\n",
    "            return ans1\n",
    "\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i >= 0:\n",
    "            j = len(nums) - 1\n",
    "            while j >= 0 and nums[i] >= nums[j]:\n",
    "                j -= 1\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "\n",
    "        left, right = i + 1, len(nums) - 1\n",
    "        while left < right:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.nextPalindrome('23143034132'))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
